Because the basis of the work in enterprises and the like has been computerized, most of those enterprises have come to carry large-scaled databases for holding a vast amount of data used in the work. Such data are important data in terms of the work. Further, also in view of protecting personal information, the data must not be leaked to the outside. Thus, in such large-scaled databases, the data to be held therein are encrypted in many cases.
However, on the contrary, usefulness of the database systems may be lost by encrypting the stored data. For example, processing for comparing the size of the numerical data and rearranging each record in order thereof can be easily done in a database in which the data is not encrypted, and such processing is executed on a daily basis. However, such processing cannot be done in a state where each data is being encrypted.
Especially in an encrypted database (secure database) server in which many users register data encrypted by encryption keys of their own client devices, it is not possible to transmit the encryption keys also to the servers for the sake of management control. Further, even if the servers have decryption keys corresponding to the respective encryption keys, a vast amount of calculation processing is required only for decrypting each data. Thus, “to execute decryption processing on each data and then compare the sizes thereof” is not practically executable processing.
Due to the recent development of the so-called cloud computing technique, it is expected in the future that there will be more and more occasions where the users transmit the own data to the database servers connected via a network to have it managed there. Therefore, it is considered that the necessity for the technique for making it possible to compare the sizes of the data stored in the database while being encrypted will be increased more and more in the future.
A technique for enabling such requirement is order-presenting encryption which is depicted in Non-Patent Documents 1 to 2. In the order-preserving encryption, when two plaintexts m and m′ is m<m′, encrypted texts Enc(K, m) and Enc(K, m′) acquired by encrypting each of those with a same encryption key also satisfies Enc(K, m)<Enc(K, m′). Therefore, through checking the relation between Enc(K, m) and Enc(K, m′) in terms of large-and-small relation thereof, it is possible to check the relation between the plaintexts m and m′ in terms of the large-and-small relation without decrypting each of those encrypted texts.
As other technical documents related thereto, there are each of following patent documents. Among those, depicted in Patent Document 1 is a bulletin board device which specifies the user who has proposed the intended largest or smallest value in electronic bidding and the like and the intended value, and keeps other confidentiality. Depicted in Patent 2 is an encryption device which expands and replaces divided plaintext data to the same size as that of the encryption key with a specific function before execution of nonlinear encryption processing.
Depicted in Patent Document 3 is a random sequence generation device used in a propagation model simulation of mobile communication and the like, which is capable of generating random numbers in accordance with specific probability distribution, standard deviation, and relative properties. Depicted in Patent 4 is a communication terminal which transmits/receives data in which a proper authentication code and a dummy authentication code are added to plaintext data. Depicted in Patent Document 5 is a device, a method, and the like for executing function calculation by secure circuit evaluation without disclosing original data.    Patent Document 1: Japanese Unexamined Patent Publication 2002-304287    Patent Document 2: Japanese Unexamined Patent Publication 2003-241656    Patent Document 3: Japanese Unexamined Patent Publication 2003-323292    Patent Document 4: Japanese Unexamined Patent Publication 2007-219157    Patent Document 5: Japanese Unexamined Patent Publication 2008-176193    Non-Patent Document 1: Alexsandra Boldyreva, Nathan Chenette, Younho Lee and Adam O'neill, Order-PreservingSymmetric Encryption, EUROCRYPT 2009. pp. 224-241.    Non-Patent Document 2: Alexsandra Boldyreva, Nathan Chenette, Adam O'neill. Order-Preserving EncryptionRevisited: Improved Security Analysis and Alternative Solutions. CRYPTO 2011: 578-595
Currently, there is no effective techniques found regarding the order-preserving encryption other than those depicted in Non-Patent Documents 1 to 2. With the order-preserving encryption depicted in Non-Patent Documents 1 to 2, it is the presupposition for achieving the technique that the numerical values of the plaintext as the target of encryption are “selected uniformly randomly from a plaintext space”. In other cases, the safety of the encryption cannot be guaranteed.
However, in the actual world, the numerical values to be the target of encryption are not necessarily limited to be “uniformly random”. For example, most of values such as human height, weight, annual income, results of academic examinations, and deviation values are distributed in a form close to a binomial distribution with respect to the average values thereof. In a case where such numerical values are taken as plaintexts, the techniques depicted in Non-Patent Documents 1 to 2 cannot be applied.
Patent Document 1 is designed to specify the maximum value and the minimum value among the encrypted numerical values. However, it is not designed to encrypt those while keeping the large-and-small relation thereof. Other Patent Documents 2 to 5 are different in object at the first place. Therefore, it is not possible to acquire the technique for making it possible to apply the technique of order-preserving encryption for the plaintexts that are “not necessarily uniformly random” even when the techniques depicted in Patent Documents 1 to 5 are combined with the techniques depicted in Non-Patent Documents 1 to 2.
It is therefore an object of the present invention to provide an order-preserving encryption system, an encryption device, a decryption device, an encryption method, a decryption method, and programs thereof capable of encrypting plaintexts while maintaining the relative large-and-small relation thereof even when numerical values that are “not necessarily uniformly random” are taken as the plaintexts.